package nachos.threads;

import nachos.machine.*;
import java.util.TreeSet;
import java.util.Iterator;
import java.util.Comparator;
/**
 * Uses the hardware timer to provide preemption, and to allow threads to sleep
 * until a certain time.
 */

public class Alarm {

    
    /**
     * Allocate a new Alarm. Set the machine's timer interrupt handler to this
     * alarm's callback.
     *
     * <p><b>Note</b>: Nachos will not function correctly with more than one
     * alarm.
     */
    public Alarm() {
	Machine.timer().setInterruptHandler(new Runnable() {
		public void run() { timerInterrupt(); }
	    });
    }

    /**
     * The timer interrupt handler. This is called by the machine's timer
     * periodically (approximately every 500 clock ticks). Causes the current
     * thread to yield, forcing a context switch if there is another thread
     * that should be run.
     */

    public void timerInterrupt() {
        WaitKThread waitingThread;

        boolean prevStatus = Machine.interrupt().disable();
        for(Iterator<WaitKThread> i = waitQueue.iterator();i.hasNext();){
           waitingThread = i.next();
           if( Machine.timer().getTime() >= waitingThread.wakeTime ){
               waitingThread.thread.ready();
               i.remove();
           }else
               break;
        }
        Machine.interrupt().restore(prevStatus);
	KThread.yield();
    }

    /**
     * Put the current thread to sleep for at least <i>x</i> ticks,
     * waking it up in the timer interrupt handler. The thread must be
     * woken up (placed in the scheduler ready set) during the first timer
     * interrupt where
     *
     * <p><blockquote>
     * (current time) >= (WaitUntil called time)+(x)
     * </blockquote>
     *
     * @param	x	the minimum number of clock ticks to wait.
     *
     * @see	nachos.machine.Timer#getTime()
     */
    public void waitUntil(long x) {
	// for now, cheat just to get something working (busy waiting is bad)
        if (x > 0){
             boolean prevStatus = Machine.interrupt().disable();
             long wakeTime = Machine.timer().getTime() + x;

             waitQueue.add(new WaitKThread(wakeTime, KThread.currentThread()));
             KThread.sleep();
             Machine.interrupt().restore(prevStatus);
        }
    }
    /*TreeSet is used for the implementation of a sortedList
     * Implemented a comparator for use with the TreeSet
     * In the timeInterrupt I only search until the waiting threads
     * must still waiting because their wakeTime haven't yet passed
     */

    private static TreeSet<WaitKThread> waitQueue = new TreeSet<WaitKThread>(new KThreadComparator());
}

class WaitKThread{
    public final long wakeTime;
    public final KThread thread;
    public WaitKThread(long w,KThread t){
        this.wakeTime = w;
        this.thread = t;
    }
    public boolean equals(WaitKThread x){
        return this.wakeTime == x.wakeTime;
    }
}
class KThreadComparator implements Comparator<WaitKThread>{
    public int compare(WaitKThread a, WaitKThread b){
        return a.wakeTime > b.wakeTime ? 1 : (a.wakeTime < b.wakeTime? -1 : 0);
    }
}